home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / snippet.exe / PBMSRCH.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-12  |  2.5 KB  |  94 lines
  1. /*
  2. **        A Pratt-Boyer-Moore string search, written by Jerry Coffin
  3. **  sometime or other in 1991.  Removed from original program, and
  4. **  (incorrectly) rewritten for seperate, generic use in early 1992.
  5. **  Corrected with help from Thad Smith, late March and early
  6. **  April 1992...hopefully it's correct this time. Revised by Bob Stout.
  7. **
  8. **  This is hereby placed in the Public Domain by its author.
  9. */
  10.  
  11. #include <stddef.h>
  12. #include <string.h>
  13. #include <limits.h>
  14.  
  15. static size_t table[UCHAR_MAX];
  16. static size_t len;
  17. static char *findme;
  18.  
  19. /*
  20. **  Call this with the string to locate to initialize the table
  21. */
  22.  
  23. void init_search(const char *string)
  24. {
  25.       size_t i;
  26.  
  27.       len = strlen(string);
  28.       for (i = 0; i < UCHAR_MAX; i++)
  29.             table[i] = len;
  30.       for (i = 0; i < len; i++)
  31.             table[(unsigned char)string[i]] = len - i - 1;
  32.       findme = (char *)string;
  33. }
  34.  
  35. /*
  36. **  Call this with a buffer to search
  37. */
  38.  
  39. char *strsearch(const char *string)
  40. {
  41.       register size_t shift;
  42.       register size_t pos = len - 1;
  43.       char *here;
  44.       size_t limit=strlen(string);
  45.  
  46.       while (pos < limit)
  47.       {
  48.             while( pos < limit &&
  49.                   (shift = table[(unsigned char)string[pos]]) > 0)
  50.             {
  51.                   pos += shift;
  52.             }
  53.             if (0 == shift)
  54.             {
  55.                   if (0 == strncmp(findme,
  56.                         here = (char *)&string[pos-len+1], len))
  57.                   {
  58.                         return(here);
  59.                   }
  60.                   else  pos++;
  61.             }
  62.       }
  63.       return NULL;
  64. }
  65.  
  66. #ifdef TEST
  67.  
  68. #include <stdio.h>
  69.  
  70. void main(void)
  71. {
  72.       char *here;
  73.       char *find_strings[] = {"abb", "you", "not", "it", "dad", "yoo", "hoo",
  74.                               "oo", "oh", "xx", "xx", "x", "x", NULL};
  75.       char *search_strings[] = {"cabbie", "your", "It isn't here",
  76.                                 "But it is here", "hodad", "yoohoo", "yoohoo",
  77.                                 "yoohoo", "yoohoo", "yoohoo", "xx", "x", "."};
  78.       int i;
  79.  
  80.       for (i = 0; find_strings[i]; i++)
  81.       {
  82.             init_search(find_strings[i]);
  83.             here = strsearch(search_strings[i]);
  84.             printf("\"%s\" is%s in \"%s\"", find_strings[i],
  85.                   here ? "" : " not", search_strings[i]);
  86.             if (here)
  87.                   printf(" [\"%s\"]", here);
  88.             putchar('\n');
  89.       }
  90.  
  91. }
  92.  
  93. #endif
  94.